package com.hh.test.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import com.hh.test.util.PrintUtil;

public class RadixSort implements Sort {

	public static void main(String[] args) {
		InputStreamReader input = new InputStreamReader(System.in);
		BufferedReader read = new BufferedReader(input);
		List<Integer> list = new ArrayList<Integer>();
		while (true) {
			try {
				String str = read.readLine();
				if (str.equals("")) {
					break;
				}
				if (str.matches("\\d*")) {
					list.add(Integer.valueOf(str));
				} else {
					System.out.println("请输入数字");
				}

			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		Sort sort = new RadixSort();
		list = Arrays.asList(1, 444, 33, 22,555,3,222,44,777,23423,23,345);
		Integer[] array = list.toArray(new Integer[list.size()]);
		PrintUtil.print(array);
		sort.sort(array);
		PrintUtil.print(array);
	}

	public void sort(Integer[] array) {
		int digit = getMaxDigit(array);
		//System.out.println("max digit:" + digit);
		for (int i = 1; i <= digit; i++) {
			sort(array, i, 10, array.length);
		}
	}

	private void sort(Integer[] array, int digit, int scale, int lengh) {
		Integer[] temp = new Integer[lengh];
		int[] buckets = new int[scale];
		for (int i = 0; i < lengh; i++) {
			buckets[getDigitValue(array[i], digit, scale)]++;
		}
		for (int i = 1; i < scale; i++) {
			buckets[i] = buckets[i - 1] + buckets[i];
		}
		for (int i = lengh - 1; i >= 0; i--) {
			int d = getDigitValue(array[i], digit, scale);
			temp[buckets[d] - 1] = array[i];
			buckets[d]--;
		}
		for (int i = 0; i < lengh; i++) {
			array[i] = temp[i];
		}
	}

	int getDigitValue(int value, int digit, int scale) {
		while (digit > 1) {
			value = value / scale;
			if (value == 0) {
				return 0;
			}
			digit--;
		}
		return value % scale;
	}

	int getMaxDigit(Integer[] array) {
		int maxDigit = 1;
		if (array != null) {
			int max = 0;
			for (Integer i : array) {
				if (i > max) {
					max = i;
				}
			}
			while (max / 10 > 0) {
				max = max / 10;
				maxDigit++;
			}
		}
		return maxDigit;
	}
}
